import java.util.Iterator;
import java.util.NoSuchElementException;

public class RandomizedQueue<Item> implements Iterable<Item> {
	private int Size;
	private int Capacity;
//	private int RandomedIndex;

	private Item[] items;
	private int first;
	private int last;
	
	@SuppressWarnings("unchecked")
	private void Resizing(int newCapacity)
	{
		int i=0;
//		Item[] oldItems = items;
		Item[] oldItems = (Item[]) new Object[Size];		
		//打乱原来的Item顺序
		for(i=0; i<Size; i++)
			oldItems[i] = items[first+i];
		StdRandom.shuffle(oldItems);

		items = (Item[]) new Object[newCapacity];
		for(i=0; i<Size; i++)
			items[i] = oldItems[i];
		first = 0;
		last = i-1;
//		RandomedIndex = last;
		
		Capacity = newCapacity;
	}
	private void checkRandom()
	{
		if(Size < Capacity/4)
		{
			Resizing(Capacity/2);
		}
		else if(Size >= Capacity)
		{
			Resizing(Capacity*2);
		}

//		else if(first > RandomedIndex || last >= Capacity-1)
		else if(last >= Capacity-1)
			Resizing(Capacity);	
	}
	
	public RandomizedQueue()                 // construct an empty randomized queue
	{
		Size = 0;
		Resizing(1);
		first = 0;
		last = -1;
	}
	public boolean isEmpty()                 // is the queue empty?
	{
		return(Size == 0);
	}
	public int size()                        // return the number of items on the queue
	{
		return Size;
	}
	public void enqueue(Item item)           // add the item
	{
		if(item == null)
			throw new java.lang.NullPointerException();
		
		int index;
		Item tmp;
		
		items[++last] = item;
		Size ++;
		//switch last & a random item
		index = StdRandom.uniform(first, last+1);
		tmp = items[index];
		items[index] = item;
		items[last] = tmp;		
		checkRandom();
	}
	public Item dequeue()                    // delete and return a random item
	{
		if(Size == 0 || last < first)
			throw new java.util.NoSuchElementException();

		checkRandom();

		Item result = items[first++];
		Size --;
		return result;
	}
	public Item sample()                     // return (but do not delete) a random item
	{
		if(Size == 0)
			throw new java.util.NoSuchElementException();
		
//		if(last == first) //Testing methods in RandomizedQueue : test 3 err
//			return items[first];
		
		return items[first + StdRandom.uniform(last-first+1)];
	}
	public Iterator<Item> iterator()         // return an independent iterator over items in random order
	{
		return new ReverseArrayIterator();
	}

	private class ReverseArrayIterator implements Iterator<Item>
	{
		private int i;
		Item[] curItems;
		@SuppressWarnings("unchecked")
		public ReverseArrayIterator()
		{
			i=0;
			curItems = (Item[]) new Object[Size];
			for(int ii=0; ii<Size; ii++)
				curItems[ii] = items[ii+first];	
			StdRandom.shuffle(curItems);
		}	

		@Override
		public boolean hasNext() {
			return (i < Size);
		}
		
		@Override
		public Item next() {
			if(i == Size)
				throw new java.util.NoSuchElementException();

			Item result = curItems[i++];
			return result;
		}
		
		@Override
		public void remove() {
			throw new java.lang.UnsupportedOperationException();
		}
		
	}
	public static void main(String[] args)   // unit testing
	{
		RandomizedQueue<Integer> queue;
		boolean errStatus;
		Iterator<Integer> iter;
		int i=0;
		int checkNum = 0;
		int TestSize = 10000;
		StdOut.println("---------Err test");
		
		errStatus = false;
		queue = new RandomizedQueue<Integer>();
		try {
			queue.dequeue();
		} catch (NoSuchElementException e) {
			errStatus = true;
		}
		if(!errStatus)
		{
			StdOut.println("new RandomizedQueue dequeue failed");
			return;
		}

		errStatus = false;
		queue = new RandomizedQueue<Integer>();
		try {
			queue.enqueue(null);
		} catch (NullPointerException e) {
			errStatus = true;
		}
		if(!errStatus)
		{
			StdOut.println("enqueue null failed");
			return;
		}
				
		errStatus = false;
		queue = new RandomizedQueue<Integer>();
		queue.enqueue(4);
		queue.dequeue();
		try {
			queue.dequeue();
		} catch (NoSuchElementException e) {
			errStatus = true;
		}
		if(!errStatus)
		{
			StdOut.println("empty RandomizedQueue dequeue failed");
			return;
		}

		queue = new RandomizedQueue<Integer>();

		errStatus = false;
		try {
			queue.iterator().next();
		} catch (NoSuchElementException e) {
			errStatus = true;
		}
		if(!errStatus)
		{
			StdOut.println("new iterator next failed");
			return;
		}
		
//		StdOut.println("---");
		i=0;
		while(i<TestSize)
		{
			queue.enqueue(i);
			i++;
		}
		iter = queue.iterator();
		while(i>0)
		{
			iter.next();
			i--;
		}
		try {
			iter.next();
		} catch (NoSuchElementException e) {
			errStatus = true;
		}
		if(!errStatus)
		{
			StdOut.println("next to end and next failed");
			return;
		}

		StdOut.println("Err test passed");		
		

		StdOut.println("---------------Function test");
		queue = new RandomizedQueue<Integer>();
		i=0;
		checkNum = 0;
		while(i<TestSize)
		{
			queue.enqueue(i);
			i++;
		}
		while(!queue.isEmpty())
		{
			checkNum += queue.dequeue();
			i--;
		}
		if(checkNum != TestSize*(TestSize-1)/2)
		{
			StdOut.println("enqueue & dequeue Total Num Err");
		}
		
		queue = new RandomizedQueue<Integer>();
		i=0;
		checkNum = 0;
		while(i<TestSize)
		{
			queue.enqueue(i);
			i++;
		}
		while(!queue.isEmpty())
		{
			if(queue.dequeue() ==  TestSize - i - 1)
				checkNum++;
			i--;
		}
		StdOut.print("Queued item count="+checkNum+" ");
		
		i=0;
		checkNum=0;
		while(i<TestSize)
		{
			queue.enqueue(i);
			i++;
		}
		while(!queue.isEmpty())
		{
			if(queue.dequeue() == i)
				checkNum++;
			i--;
		}
		StdOut.println("Reversied item count="+checkNum);
		
		queue = new RandomizedQueue<Integer>();
		i=0;
		checkNum = 0;
		while(i<TestSize)
		{
			queue.enqueue(i);
			i++;
		}
		iter = queue.iterator();
		while(iter.hasNext())
		{
			int tmp = iter.next();
//			StdOut.println(tmp);
			if(tmp == TestSize - i - 1)
				checkNum++;
			i--;
		}
		StdOut.print("Queued iterator count="+checkNum+" ");

		queue = new RandomizedQueue<Integer>();
		i=0;
		checkNum = 0;
		while(i<TestSize)
		{
			queue.enqueue(i);
			i++;
		}
		iter = queue.iterator();
		while(iter.hasNext())
		{
			int tmp = iter.next();
//			StdOut.println(tmp);
			if(tmp == i)
				checkNum++;
			i--;
		}
		StdOut.println("Reversied iterator count="+checkNum+" ");

		queue = new RandomizedQueue<Integer>();
		i=0;
		checkNum = 0;
		while(i<TestSize)
		{
			queue.enqueue(i);
			i++;
		}
		int oldvalue = queue.sample();
		int newvalue;
		while(i>0)
		{
			newvalue = queue.sample();
			if(oldvalue == newvalue)
				checkNum++;
			oldvalue = newvalue;
			i--;
		}
		StdOut.println("Repeated sample() count="+checkNum);
		
		queue = new RandomizedQueue<Integer>();
		i=0;
		checkNum = 0;
		while(i<TestSize)
		{
			queue.enqueue(i);
			i++;
		}
		iter = queue.iterator();
		Iterator<Integer> iter1 = queue.iterator();
		while(iter.hasNext())
		{
			if(iter1.next() == iter.next())
				checkNum++;
		}
		StdOut.println("Mutiple iterator same count="+checkNum);
		
		StdOut.println("\n-------zuoye test check");

		queue = new RandomizedQueue<Integer>();
		i=0;
		checkNum = 0;
		queue.enqueue(i);
		queue.sample();
		StdOut.println("Testing methods in RandomizedQueue : Test3 passed");
		
		queue = new RandomizedQueue<Integer>();
		i=0;
		checkNum = 0;
		queue.enqueue(i);
		queue.enqueue(i);
		queue.dequeue();
		queue.sample();
		StdOut.println("Testing methods in RandomizedQueue : Test4 passed");
		
		i=0;
		checkNum = 0;
		int times = 0;
		int[] results = new int[10];
		results[0] = results[1] = results[2] = 0;
		while(i<TestSize)
		{
			queue = new RandomizedQueue<Integer>();
			queue.enqueue(1);
			queue.enqueue(2);
			queue.enqueue(3);
			queue.enqueue(4);
			queue.enqueue(5);
			queue.enqueue(6);
			queue.enqueue(7);
			queue.enqueue(8);
			queue.enqueue(9);
			queue.enqueue(10);
			times = 0;
			do
			{
				checkNum = queue.dequeue();
				times++;
			}while(checkNum != 1);
			results[times-1] ++;
			i++;
		}
		double stdValue = 0.0;
		for(i=0; i<10; i++)
		{
			stdValue += (double)((results[i] - 1000)*(results[i]-1000))/1000;
		}
//		stdValue = Math.sqrt(stdValue);
		if(stdValue < 10.83)
			StdOut.println("Testing methods in RandomizedQueue : Test13 passed");
		else
			StdOut.println("Testing methods in RandomizedQueue : Test13 failed : stdValue="+stdValue);
		
		RandomizedQueue<String> strque = new RandomizedQueue<String>();
		i=0;
		while(i<100)
		{
			strque.enqueue("test");
//			i++;
//		}
//		while(i>0)
//		{
			strque.dequeue();
			i++;
		}
		
		StdOut.println("Computing memory of RandomizedQueue : Test 6 passed");
		StdOut.println("Funciton test passed");
		
//		StdOut.println("----------Performance calc");
//		i=1;
//		while(i*2 < TestSize/4)
//			i*=2;
//		
//		RandomizedQueue queue1, queue2;
//		
		
		
	}
}